#include <assert.h>
#include <stdlib.h>

#include "zip_utils.h"
#include "dig_domain_rbtree.h"
#include "dig_atomic.h"

#define	BLACK	0
#define	RED	1


struct domain_rbnode
{
    domain_rbnode_t *parent_;
    domain_rbnode_t *left_;
    domain_rbnode_t *right_;
    uint8_t         color_;

    //dns related 
    struct wire_name *name_;
    const void *data_;
    domain_rbnode_t *down_;
    
    uint8_t  locknum_;
    atomic_t ref_count_;


    unsigned int needs_callback_:1;
};

#define RBNODE_NULL &_null_node
static domain_rbnode_t _null_node = {
	RBNODE_NULL,		// Parent. 
	RBNODE_NULL,		// Left.  
	RBNODE_NULL,		// Right. 
	BLACK,			    // color

    NULL,               //name
    NULL,               //data
    RBNODE_NULL,        //down
    0                   //needs callback
};
#define DOMAIN_RBNODE_IS_NULL(node) ((node) == RBNODE_NULL)
#define DOMAIN_RBNODE_IS_EMPTY(node) ((node)->data_ == NULL)
#define DOMAIN_RBNODE_IS_LEAF(node) (DOMAIN_RBNODE_IS_NULL(node->left_) && DOMAIN_RBNODE_IS_NULL(node->right_))

static domain_rbnode_t *
domain_rbnode_create(const wire_name_t *name)
{
    domain_rbnode_t *node = RBNODE_NULL;
    DIG_MALLOC(node, sizeof(domain_rbnode_t));
    if (node)
    {
        node->name_ = wire_name_clone(name);
        node->parent_ = node->left_ = node->right_ = node->down_ = RBNODE_NULL;
        node->color_ = RED;
        node->data_ = NULL;
        node->locknum_ = 0;
        node->needs_callback_ = 0;
        atomic_set(&(node->ref_count_), 0);
    }

    return node;
}

void domain_rbnode_delete(domain_rbnode_t *node)
{
    ASSERT(!DOMAIN_RBNODE_IS_NULL(node), "delete null node\n");
    wire_name_delete(node->name_);
    free(node);
}   

const wire_name_t *
domain_rbnode_get_name(const domain_rbnode_t *node)
{
    return node->name_;
}

const void* 
domain_rbnode_get_data(const domain_rbnode_t *node)
{
    return node->data_;
}

void
domain_rbnode_set_data(domain_rbnode_t *node, const void *data)
{
    node->data_ = data;
}

void
domain_rbnode_set_locknum(domain_rbnode_t *node, uint8_t locknum)
{
    node->locknum_ = locknum;
}

uint8_t
domain_rbnode_get_locknum(const domain_rbnode_t *node)
{
    return node->locknum_;
}

void
domain_rbnode_retain(domain_rbnode_t *node)
{
    atomic_inc(&(node->ref_count_));
}

bool
domain_rbnode_release(domain_rbnode_t *node)
{
    return atomic_dec_and_test(&(node->ref_count_));
}

int
domain_rbnode_get_reference_count(const domain_rbnode_t *node)
{
    return atomic_read(&(node->ref_count_));
}

bool
domain_rbnode_is_null(const domain_rbnode_t *node)
{
    return DOMAIN_RBNODE_IS_NULL(node);
}

bool                    
domain_rbnode_is_empty(const domain_rbnode_t *node)
{
    return DOMAIN_RBNODE_IS_EMPTY(node);
}

const domain_rbnode_t *
domain_rbnode_successor(const domain_rbnode_t *node)
{
    const domain_rbnode_t *current = node;
    if (!DOMAIN_RBNODE_IS_NULL(node->right_)) {
        current = node->right_;
        while (!DOMAIN_RBNODE_IS_NULL(current->left_)) {
            current = current->left_;
        }    
        return current;
    }    

    const domain_rbnode_t* parent = current->parent_;
    while (!DOMAIN_RBNODE_IS_NULL(parent) && current == parent->right_) {
        current = parent;
        parent = parent->parent_;
    }    
    return parent;
}

const domain_rbnode_t*
domain_rbnode_predecessor(const domain_rbnode_t *node)
{
    const domain_rbnode_t *current = node;
    if (!DOMAIN_RBNODE_IS_NULL(current->left_))
    {
        current = current->left_;
        while (!DOMAIN_RBNODE_IS_NULL(current->right_))
            current = current->right_;
        return current;
    }

    const domain_rbnode_t *parent = current->parent_;
    while (!DOMAIN_RBNODE_IS_NULL(parent) && current == parent->left_)
    {
        current = parent;
        parent = parent->parent_;
    }
    return parent;
}



void 
domain_rbnode_set_callback(domain_rbnode_t *node, bool needs_callback)
{
    node->needs_callback_ = needs_callback ? 1 : 0;
}

bool 
doname_rbnode_needs_callback(const domain_rbnode_t *node)
{
    return node->needs_callback_ == 1;
}

bool
domain_rbnode_has_child(const domain_rbnode_t *node)
{
    return false == DOMAIN_RBNODE_IS_NULL(node->down_);
}


/*
 * domain node chain code
 * */

struct domain_rbnode_chain
{
    const domain_rbnode_t *nodes_[MAX_LABEL_COUNT];
    uint32_t node_count_;
};


domain_rbnode_chain_t *
domain_chain_create()
{
    domain_rbnode_chain_t *chain = NULL;
    DIG_MALLOC(chain, sizeof(domain_rbnode_chain_t));
    if (chain)
        chain->node_count_ = 0;
    return chain;
}

domain_rbnode_chain_t *
domain_chain_copy(domain_rbnode_chain_t *path)
{
    domain_rbnode_chain_t *chain = domain_chain_create();
    if (NULL == chain)
        return NULL;

    int i = 0;
    for (; i < path->node_count_; ++i)
    {
        (chain->nodes_)[i] = (path->nodes_)[i];
        domain_rbnode_retain((domain_rbnode_t *)((chain->nodes_)[i]));
    }
    chain->node_count_ = path->node_count_;

    return chain;
}

void 
domain_chain_delete(domain_rbnode_chain_t *path)
{
    domain_chain_clear(path);
    free(path);
}

static bool
domain_chain_is_empty(const domain_rbnode_chain_t *path)
{
    return path->node_count_ == 0;
}

static void
domain_chain_push(domain_rbnode_chain_t *path, const domain_rbnode_t *node)
{
    ASSERT(path->node_count_ < MAX_LABEL_COUNT, "node count exceed max label count");
    domain_rbnode_retain((domain_rbnode_t *)node);
    path->nodes_[path->node_count_] = node;
    ++path->node_count_;
}

void
domain_chain_pop(domain_rbnode_chain_t *path)
{
    ASSERT(!domain_chain_is_empty(path), "pop empty node chain");
    domain_rbnode_release((domain_rbnode_t *)domain_chain_top(path));
    --path->node_count_;
}

void
domain_chain_clear(domain_rbnode_chain_t *path)
{
    int i = 0;
    for (; i < path->node_count_; ++i)
    {
        domain_rbnode_t *node = (domain_rbnode_t *)(path->nodes_)[i];
        domain_rbnode_release(node);
    }
    path->node_count_ = 0;
}

const domain_rbnode_t *
domain_chain_top(const domain_rbnode_chain_t *path)
{
    ASSERT(!domain_chain_is_empty(path), "get last node on empty node chain\n");
    return path->nodes_[path->node_count_ - 1];
}

uint32_t 
domain_chain_get_node_count(const domain_rbnode_chain_t *path)
{
    return path->node_count_;
}
/*
 * domain rbtree 
 * */
struct domain_rbtree 
{
    domain_rbnode_t *root_;
    unsigned int node_count_;
    bool needs_return_empty_node_;

    domain_rbtree_value_deleter_t deleter_;
};


#define INDENT_FOR_EACH_DEPTH 5
#define INDENT(buf, depth, len) do {\
    (len) = (depth) * INDENT_FOR_EACH_DEPTH;\
    uint32_t each_write_len = 0, i = 0;\
    for (; i < (len); ++i){ \
        each_write_len = buffer_write_u8(buf, ' ');\
        if (each_write_len == 0) break;\
    }\
    if (each_write_len == 0) len = 0;\
}while(0)

/* 
 * find the target name from the top node of node_path
 * so the caller should garantee that the node_path isn't empty
 * and the top node is the ancestor of target name
 * */
inline static domain_rbtree_find_result_t 
_domain_rbtree_continue_find(const domain_rbtree_t *tree,
                             const wire_name_t *name,
                             domain_rbnode_t ** target,
                             domain_rbnode_chain_t *node_path,
                             domain_rbnode_callback_t callback,
                             void *callback_arg);
inline static bool 
_domain_rbtree_prev_node(const domain_rbtree_t *tree, 
                        domain_rbnode_chain_t *node_path,
                        const domain_rbnode_t **prev_node);
inline static bool 
_domain_rbtree_next_node(const domain_rbtree_t *tree, 
                        domain_rbnode_chain_t *node_path,
                        const domain_rbnode_t **next_node);

static uint32_t domain_rbtree_delete_helper(domain_rbnode_t* root, uint32_t node_count, domain_rbtree_value_deleter_t deleter);
static void domain_rbtree_delete_domain_helper(domain_rbnode_t **root, domain_rbnode_t *node, domain_rbtree_value_deleter_t deleter);
static domain_rbnode_t * domain_rbtree_left_rotate(domain_rbnode_t** root, domain_rbnode_t* node);
static domain_rbnode_t * domain_rbtree_right_rotate(domain_rbnode_t** root, domain_rbnode_t* node);
static void domain_rbtree_insert_rebalance(domain_rbnode_t **root, domain_rbnode_t *node);
static void domain_rbtree_delete_rebalance(domain_rbnode_t **root, domain_rbnode_t *parent, domain_rbnode_t *node);
static uint32_t domain_rbtree_to_text_helper(buffer_t *buf, domain_rbnode_t *node, uint32_t depth);

domain_rbtree_t *
domain_rbtree_create(const wire_name_t *root_name, domain_rbtree_value_deleter_t deleter)
{
    ASSERT(deleter != NULL, "the deleter for domain rbtree shouldn't be NULL");
    domain_rbtree_t *tree = NULL;
    DIG_MALLOC(tree, sizeof(domain_rbtree_t));
    if (tree)
    {
        tree->root_ = domain_rbnode_create(root_name);
        if (tree->root_ == NULL)
        {
            free(tree);
            return NULL;
        }
        tree->root_->color_ = BLACK;
        tree->node_count_ = 1;
        tree->needs_return_empty_node_ = false;
        tree->deleter_ = deleter;
    }

    return tree;
}

void domain_rbtree_delete(domain_rbtree_t *rbtree)
{
    uint32_t left_node_count = domain_rbtree_delete_helper(rbtree->root_, rbtree->node_count_, rbtree->deleter_);
    ASSERT(left_node_count == 0, "all nodes should be deleted %d", left_node_count);
}

static uint32_t 
domain_rbtree_delete_helper(domain_rbnode_t* root, uint32_t node_count, domain_rbtree_value_deleter_t deleter)
{
    uint32_t left_node_count = node_count;
    if (root == RBNODE_NULL) 
        return left_node_count;

    domain_rbnode_t* node = root;
    while (!DOMAIN_RBNODE_IS_LEAF(root))
    {
        while (!DOMAIN_RBNODE_IS_LEAF(node))
            node = domain_rbnode_is_null(node->left_) ? node->right_ : node->left_;

        domain_rbnode_t* parent = node->parent_;
        if (parent->left_ == node) 
            parent->left_ = RBNODE_NULL;
        else 
            parent->right_ = RBNODE_NULL;
        

        left_node_count = domain_rbtree_delete_helper(node->down_, left_node_count, deleter);
        if (deleter)
            (*deleter)((void *)(node->data_));
        domain_rbnode_delete(node);

        
        --left_node_count;
        node = parent;
    }

    left_node_count = domain_rbtree_delete_helper(root->down_, left_node_count, deleter);
    if (deleter)
        (*deleter)((void *)(root->data_));
    domain_rbnode_delete(root);
    return --left_node_count;
}

domain_rbnode_t *
domain_rbtree_get_root_node(domain_rbtree_t *tree)
{
    ASSERT(tree->root_ != NULL, "once the tree is alive so be its root node");
    return tree->root_;
}

uint32_t
domain_rbtree_get_node_count(const domain_rbtree_t *tree)
{
    return tree->node_count_;
}

domain_rbtree_find_result_t 
domain_rbtree_find(const domain_rbtree_t *tree,
                   const wire_name_t *name,
                   domain_rbnode_t ** target,
                   domain_rbnode_chain_t *node_path,
                   domain_rbnode_callback_t callback,
                   void *callback_arg)
{
    ASSERT(domain_chain_is_empty(node_path), "domain rbtree find is given non empty chain");
    ASSERT(!DOMAIN_RBNODE_IS_NULL(tree->root_), "tree root is empty\n");
    ASSERT(wire_name_contains(name, tree->root_->name_), "search name aren't in current zone\n");

    //full compare with root, root should either sub domain of target name, 
    //or equal to target name
    domain_chain_push(node_path, tree->root_);
    if (wire_name_is_equal(tree->root_->name_, name))
    {
        *target = tree->root_;
        return EXACTMATCH;
    }

    return _domain_rbtree_continue_find(tree, name, target, node_path, callback, callback_arg);
}


inline static domain_rbtree_find_result_t 
_domain_rbtree_continue_find(const domain_rbtree_t *tree,
                             const wire_name_t *name,
                             domain_rbnode_t ** target,
                             domain_rbnode_chain_t *node_path,
                             domain_rbnode_callback_t callback,
                             void *callback_arg)
{
    ASSERT(!domain_chain_is_empty(node_path), "node path shouldn't be empty\n");
    domain_rbnode_t *node = domain_chain_top(node_path)->down_;
    if (DOMAIN_RBNODE_IS_NULL(node))
        return NOTFOUND;


    domain_rbtree_find_result_t ret = NOTFOUND;
    //compare the leftest label
    int compare_label_index = wire_name_get_label_count(node->name_) - 1;
    uint8_t target_name_label_count = wire_name_get_label_count(name);
    int compare_order = 0;
    while (!DOMAIN_RBNODE_IS_NULL(node))
    {
        compare_order = wire_name_label_compare(name, node->name_, compare_label_index);
        if (compare_order == 0) 
        {
            domain_chain_push(node_path, node);
            if (compare_label_index + 1 == target_name_label_count)
            {
                if (tree->needs_return_empty_node_ || !domain_rbnode_is_empty(node))
                {
                    if (node->needs_callback_ && callback)
                        if (!(*callback)(node, callback_arg))
                            return FIND_INTERRUPT_BY_CALL_BACK;

                    *target = node;
                    ret = EXACTMATCH;
                }
                break;
            }
            else 
            {
                ret = PARTIALMATCH;
                if (node->needs_callback_ && callback)
                    if (!(*callback)(node, callback_arg))
                        return FIND_INTERRUPT_BY_CALL_BACK;
                node = node->down_;
            }
            ++compare_label_index;
        }
        else if (compare_order < 0)
            node = node->left_;
        else
            node = node->right_;
    }

    return ret;
}

domain_rbtree_find_result_t 
domain_rbtree_continue_find(const domain_rbtree_t *tree,
                            const wire_name_t *name,
                            domain_rbnode_t ** node,
                            domain_rbnode_chain_t *node_path,
                            domain_rbnode_callback_t callback,
                            void *callback_arg)
{
   if (domain_chain_is_empty(node_path))
       return domain_rbtree_find(tree, name, node, node_path, callback, callback_arg);

   return _domain_rbtree_continue_find(tree, name, node, node_path, callback, callback_arg);
}

domain_rbtree_find_result_t 
domain_rbtree_simple_find(const domain_rbtree_t *tree,
                          const wire_name_t *name,
                          domain_rbnode_t **node)
{
    domain_rbnode_chain_t *chain = domain_chain_create();
    domain_rbtree_find_result_t ret = domain_rbtree_find(tree, name, node, chain, NULL, NULL);
    domain_chain_delete(chain);
    return ret;
}


bool 
domain_rbtree_next_node(const domain_rbtree_t *tree, 
                        domain_rbnode_chain_t *node_path,
                        const domain_rbnode_t **next_node)
{
    while (_domain_rbtree_next_node(tree, node_path, next_node))
    {
        if (!DOMAIN_RBNODE_IS_EMPTY(*next_node) || tree->needs_return_empty_node_)
            return true;
    }

    return false;
}

bool 
domain_rbtree_prev_node(const domain_rbtree_t *tree, 
                        domain_rbnode_chain_t *node_path,
                        const domain_rbnode_t **prev_node)
{
    while (_domain_rbtree_prev_node(tree, node_path, prev_node))
    {
        if (!DOMAIN_RBNODE_IS_EMPTY(*prev_node) || tree->needs_return_empty_node_)
            return true;
    }

    return false;
}

inline static bool 
_domain_rbtree_next_node(const domain_rbtree_t *tree, 
                        domain_rbnode_chain_t *node_path,
                        const domain_rbnode_t **next_node)
{
    ASSERT(!domain_chain_is_empty(node_path), "node path in next node shouldn't be empty");
    const domain_rbnode_t *node = domain_chain_top(node_path);


    if (!DOMAIN_RBNODE_IS_NULL(node->down_))
    {
        const domain_rbnode_t *left_most = node->down_;
        while (!DOMAIN_RBNODE_IS_NULL(left_most->left_))
            left_most = left_most->left_;
        domain_chain_push(node_path, left_most);
        *next_node = left_most;
        return true;
    }    

    domain_chain_pop(node_path);
    const domain_rbnode_t *successor = domain_rbnode_successor(node);
    if (!DOMAIN_RBNODE_IS_NULL(successor))
    {
        domain_chain_push(node_path, successor);
        *next_node = successor;
        return true;
    }    

    while (!domain_chain_is_empty(node_path))
    {
        const domain_rbnode_t *up_node_successor = domain_rbnode_successor(domain_chain_top(node_path));
        domain_chain_pop(node_path);
        if (!DOMAIN_RBNODE_IS_NULL(up_node_successor))
        {
            domain_chain_push(node_path, up_node_successor);
            *next_node = up_node_successor;
            return true;
        }
    }

    return false;
}

inline static bool 
_domain_rbtree_prev_node(const domain_rbtree_t *tree, 
                         domain_rbnode_chain_t *node_path,
                         const domain_rbnode_t **prev_node)
{
    ASSERT(!domain_chain_is_empty(node_path), "node path in next node shouldn't be empty");
    const domain_rbnode_t *node = domain_chain_top(node_path);
    domain_chain_pop(node_path);

    const domain_rbnode_t *predecessor = domain_rbnode_predecessor(node);
    if (!DOMAIN_RBNODE_IS_NULL(predecessor))
    {
        domain_chain_push(node_path, predecessor);
        while (!DOMAIN_RBNODE_IS_NULL(predecessor->down_))
        {
            predecessor = predecessor->down_;
            while (!DOMAIN_RBNODE_IS_NULL(predecessor->right_))
                predecessor = predecessor->right_;
            domain_chain_push(node_path, predecessor);
        }
    }

    if (domain_chain_get_node_count(node_path) > 0)
    {
        *prev_node = domain_chain_top(node_path);
        return true;
    }
    else
        return false;
}

bool 
domain_rbtree_first_node(const domain_rbtree_t *tree, 
                         domain_rbnode_chain_t *node_path,
                         const domain_rbnode_t **first_node)
{
    ASSERT(domain_chain_is_empty(node_path), "node path should be empty for first node");
    domain_chain_push(node_path, tree->root_);
    *first_node = tree->root_;

    if (!DOMAIN_RBNODE_IS_EMPTY(*first_node) || tree->needs_return_empty_node_)
        return true;
    else
        return domain_rbtree_next_node(tree, node_path, first_node);
}

bool 
domain_rbtree_last_node(const domain_rbtree_t *tree, 
                        domain_rbnode_chain_t *node_path,
                        const domain_rbnode_t **last_node)
{
    ASSERT(domain_chain_is_empty(node_path), "node path should be empty for last node");
    const domain_rbnode_t *current_node = tree->root_;
    do 
    {
        while (!DOMAIN_RBNODE_IS_NULL(current_node->right_))
            current_node = current_node->right_;
        
        domain_chain_push(node_path, current_node);
        if (DOMAIN_RBNODE_IS_NULL(current_node->down_))
            break;
        current_node = current_node->down_;

    } while(1);

    *last_node = domain_chain_top(node_path);

    if (!DOMAIN_RBNODE_IS_EMPTY(*last_node) || tree->needs_return_empty_node_)
        return true;
    else
        return domain_rbtree_prev_node(tree, node_path, last_node);
}


void 
domain_rbtree_set_return_nonterminal(domain_rbtree_t *tree, bool does_return_nonterminal)
{
    tree->needs_return_empty_node_ = does_return_nonterminal;
}

domain_rbnode_t *
domain_rbtree_insert_domain(domain_rbtree_t *tree, 
                            const wire_name_t *name,
                            domain_non_terminal_rbnode_create_callback_t callback,
                            void *parameter)
{
    ASSERT(!DOMAIN_RBNODE_IS_NULL(tree->root_), "tree root node is empty\n");

    uint8_t root_name_label_count = wire_name_get_label_count(tree->root_->name_);
    uint8_t target_name_label_count = wire_name_get_label_count(name);
    ASSERT(target_name_label_count >= root_name_label_count, "search name is shorter than root name\n");

    //full compare with root, root should either sub domain of target name, 
    //or equal to target name
    if (wire_name_is_equal(tree->root_->name_, name))
        return tree->root_;

    domain_rbnode_t *parent = RBNODE_NULL;
    domain_rbnode_t *current = tree->root_->down_;
    domain_rbnode_t *upnode = tree->root_;
    int compare_label_index = wire_name_get_label_count(tree->root_->name_);
    int order = 0;
    while (!DOMAIN_RBNODE_IS_NULL(current))
    {
        order = wire_name_label_compare(name, current->name_, compare_label_index);
        if (order == 0)
        {
            if (compare_label_index + 1 == target_name_label_count)
                return current;
            else
            {
                upnode = current;
                parent = RBNODE_NULL;
                current = current->down_;
                ++compare_label_index;
            }
        }
        else 
        {
            parent = current;
            if (order < 0)
                current = parent->left_;
            else
                current = parent->right_;
        }
    }

    domain_rbnode_t *new_node = RBNODE_NULL;
    //add non-terminal nodes
    while (compare_label_index < target_name_label_count)
    {
        wire_name_t *new_node_name = NULL;
        wire_name_split(name, target_name_label_count - compare_label_index - 1, NULL, &new_node_name);
        new_node = domain_rbnode_create(new_node_name);
        wire_name_delete(new_node_name);
        if (order != 0)
        {
            domain_rbnode_t** current_root = &(upnode->down_);
            new_node->parent_ = parent;
            ASSERT(!DOMAIN_RBNODE_IS_NULL(parent), "parent shouldn't be null node if has compared in one tree\n");
            if (order < 0) 
                parent->left_ = new_node;
            else 
                parent->right_ = new_node;
            
            domain_rbtree_insert_rebalance(current_root, new_node);
            order = 0;
        }
        else
        {
            upnode->down_ = new_node;
            new_node->color_ = BLACK;
        }
        upnode = new_node;
        ++tree->node_count_;
        ++compare_label_index;

        //call the non-terminal node call back function
        if (compare_label_index < target_name_label_count && callback)
            (*callback)(new_node, parameter);
    }

    return new_node;
}


static void
domain_rbtree_insert_rebalance(domain_rbnode_t **root, domain_rbnode_t *node)
{
    domain_rbnode_t *uncle = RBNODE_NULL;
    while (node != *root && node->parent_->color_ == RED) 
    {
        if (node->parent_ == node->parent_->parent_->left_) 
        {
            uncle = node->parent_->parent_->right_;

            if (uncle->color_ == RED) 
            {
                node->parent_->color_ = BLACK;
                uncle->color_ = BLACK;
                node->parent_->parent_->color_ = RED;
                node = node->parent_->parent_;
            } 
            else 
            {
                if (node == node->parent_->right_) 
                {
                    node = node->parent_;
                    domain_rbtree_left_rotate(root, node);
                }
                node->parent_->color_ = BLACK;
                node->parent_->parent_->color_ = RED;
                domain_rbtree_right_rotate(root, node->parent_->parent_);
            }
        } 
        else 
        {
            uncle = node->parent_->parent_->left_;
            if (uncle->color_ == RED) 
            {
                node->parent_->color_ = BLACK;
                uncle->color_ = BLACK;
                node->parent_->parent_->color_ = RED;
                node = node->parent_->parent_;
            } 
            else 
            {
                if (node == node->parent_->left_) 
                {
                    node = node->parent_;
                    domain_rbtree_right_rotate(root, node);
                }
                node->parent_->color_ = BLACK;
                node->parent_->parent_->color_ = RED;
                domain_rbtree_left_rotate(root, node->parent_->parent_);
            }        
        }
    }

    (*root)->color_ = BLACK;
}

static void
domain_rbtree_delete_rebalance(domain_rbnode_t **root, domain_rbnode_t *parent, domain_rbnode_t *node)
{
    domain_rbnode_t *other = RBNODE_NULL;
    while ((!DOMAIN_RBNODE_IS_NULL(node) || node->color_ == BLACK) && node != *root)
    {
        if (parent->left_ == node)
        {
            other = parent->right_;
            if (other->color_ == RED)
            {
                other->color_ = BLACK;
                parent->color_ = RED;
                domain_rbtree_left_rotate(root, parent);
                other = parent->right_;
            }
            if ((!DOMAIN_RBNODE_IS_NULL(other->left_) || other->left_->color_ == BLACK) &&
                (!DOMAIN_RBNODE_IS_NULL(other->right_) || other->right_->color_ == BLACK))
            {
                other->color_ = RED;
                node = parent;
                parent = node->parent_;
            }
            else
            {
                if (!DOMAIN_RBNODE_IS_NULL(other->right_) || other->right_ == BLACK)
                {
                    other->left_->color_ = BLACK;
                    other->color_ = RED;
                    domain_rbtree_right_rotate(root, other);
                    other = parent->right_;
                }
                other->color_ = parent->color_;
                parent->color_ = BLACK;
                other->right_->color_ = BLACK;
                domain_rbtree_left_rotate(root, parent);
                node = *root;
                break;
            }
        }
        else
        {
            other = parent->left_;
            if (other->color_ == RED)
            {
                other->color_ = BLACK;
                parent->color_ = RED;
                domain_rbtree_right_rotate(root, parent);
                other = parent->left_;
            }
            if ((!DOMAIN_RBNODE_IS_NULL(other->left_) || other->left_->color_ == BLACK) &&
                (!DOMAIN_RBNODE_IS_NULL(other->right_) || other->right_->color_ == BLACK))
            {
                other->color_ = RED;
                node = parent;
                parent = node->parent_;
            }
            else
            {
                if(!DOMAIN_RBNODE_IS_NULL(other->left_) || other->left_->color_ == BLACK)
                {
                    other->right_->color_ = BLACK;
                    other->color_ = RED;
                    domain_rbtree_left_rotate(root, other);
                    other = parent->left_;
                }
                other->color_ = parent->color_;
                parent->color_ = BLACK;
                other->left_->color_ = BLACK;
                domain_rbtree_right_rotate(root, parent);
                node = *root;
                break;
            }
        }
    }
    if (DOMAIN_RBNODE_IS_NULL(node))
        node->color_ = BLACK;
}

static domain_rbnode_t *
domain_rbtree_left_rotate(domain_rbnode_t** root, domain_rbnode_t* node) 
{
    domain_rbnode_t* right = node->right_;
    node->right_ = right->left_;
    if (!DOMAIN_RBNODE_IS_NULL(right->left_)) 
        right->left_->parent_ = node;

    right->parent_ = node->parent_;

    if (!DOMAIN_RBNODE_IS_NULL(node->parent_)) 
    {
        if (node == node->parent_->left_) 
            node->parent_->left_ = right;
        else  
            node->parent_->right_ = right;
    } else 
        *root = right;
    
    right->left_ = node;
    node->parent_ = right;
    return node;
}

static domain_rbnode_t *
domain_rbtree_right_rotate(domain_rbnode_t **root, domain_rbnode_t *node)
{
    domain_rbnode_t *left = node->left_;
    node->left_ = left->right_;
    if (!DOMAIN_RBNODE_IS_NULL(left->right_))
        left->right_->parent_ = node;

    left->parent_ = node->parent_;

    if (!DOMAIN_RBNODE_IS_NULL(node->parent_))
    {
        if (node == node->parent_->right_) 
            node->parent_->right_ = left;
        else  
            node->parent_->left_ = left;
    } 
    else 
        *root = left;
    
    left->right_ = node;
    node->parent_ = left;
    return node;
}


bool
domain_rbtree_delete_domain(domain_rbtree_t *tree, 
                            const wire_name_t *name,
                            const domain_rbnode_t **undel_parent_node,
                            domain_rbnode_is_non_terminal_callback_t is_non_terminal_checker,
                            void *parameter)
{
    domain_rbnode_t *node = RBNODE_NULL;
    domain_rbnode_chain_t *node_path = domain_chain_create();
    if (domain_rbtree_find(tree, name, &node, node_path, NULL, NULL) != EXACTMATCH)
    {
        domain_chain_delete(node_path);
        return false;
    }

    if (node && (domain_rbnode_get_reference_count(node) > 1))
    {
        domain_chain_delete(node_path);
        return false;
    }

    //if node has sub domain or it's root node, we just make it empty
    if (!DOMAIN_RBNODE_IS_NULL(node->down_) || node == tree->root_)
    {
        (*(tree->deleter_))((void *)(node->data_));
        node->data_ = NULL;
        if (undel_parent_node)
            *undel_parent_node = node;
    }
    else
    {
        domain_chain_pop(node_path);
        domain_rbnode_t *upnode = (domain_rbnode_t *)domain_chain_top(node_path);
        domain_rbnode_t **root = &(upnode->down_);
        domain_rbtree_delete_domain_helper(root, node, tree->deleter_);
        --tree->node_count_;

        // if node is the last node in the sub domain tree
        // we will keep delete the non-terminal up nodes until the root node
        // there will still be one node(root node) even the rbtree is empty
        while (domain_chain_get_node_count(node_path) > 1)
        {
            domain_rbnode_t *upnode = (domain_rbnode_t *)domain_chain_top(node_path);
            if (DOMAIN_RBNODE_IS_NULL(upnode->down_) && 
                (domain_rbnode_is_empty(upnode) || (is_non_terminal_checker && (*is_non_terminal_checker)(upnode, parameter))))
            {
                node = upnode;
                domain_chain_pop(node_path);
                upnode = (domain_rbnode_t *)domain_chain_top(node_path);
                domain_rbnode_t **root = &(upnode->down_);
                domain_rbtree_delete_domain_helper(root, node, tree->deleter_);
                --tree->node_count_;
            }
            else
            {
                if (undel_parent_node)
                    *undel_parent_node = upnode;
                break;
            }
        }
    }

    domain_chain_delete(node_path);
    return true;
}

static void 
domain_rbtree_delete_domain_helper(domain_rbnode_t **root, domain_rbnode_t *node, domain_rbtree_value_deleter_t deleter)
{
    domain_rbnode_t *child = RBNODE_NULL;
    domain_rbnode_t *parent = RBNODE_NULL;
    int color;
    if (DOMAIN_RBNODE_IS_NULL(node->left_))
        child = node->right_;
    else if (DOMAIN_RBNODE_IS_NULL(node->right_))
        child = node->left_;
    else
    {
        domain_rbnode_t *old = node;
        node = node->right_;
        while (!DOMAIN_RBNODE_IS_NULL(node->left_))
            node = node->left_;

        if (!DOMAIN_RBNODE_IS_NULL(old->parent_))
        {
            if (old->parent_->left_ == old)
                old->parent_->left_ = node;
            else
                old->parent_->right_ = node;
        } else
            *root = node;

        child = node->right_;
        parent = node->parent_;
        color = node->color_;

        if (parent == old) {
            parent = node;
        } else {
            if (!DOMAIN_RBNODE_IS_NULL(child))
                child->parent_ = parent;
            parent->left_ = child;
            node->right_ = old->right_;
            old->right_->parent_ = node;
        }

        node->parent_ = old->parent_;
        node->left_ = old->left_;
        old->left_->parent_ = node;
        if (color == BLACK)
            domain_rbtree_delete_rebalance(root, parent, node);

        (*deleter)((void *)(old->data_));
        domain_rbnode_delete(old);
        return;
    }

    parent = node->parent_;
    color = node->color_;
    if (!DOMAIN_RBNODE_IS_NULL(child))
        child->parent_ = parent;
    if (!DOMAIN_RBNODE_IS_NULL(parent))
    {
        if (parent->left_ == node)
            parent->left_ = child;
        else
            parent->right_ = child;
    }
    else
        *root = child;

    (*deleter)((void *)(node->data_));
    domain_rbnode_delete(node);
}

uint32_t 
domain_rbtree_to_text(const domain_rbtree_t *tree, buffer_t *buf)
{
    size_t roll_back_pos = buffer_position(buf);
    if (0 == buffer_printf(buf, "tree has nodes(%d)\n", domain_rbtree_get_node_count(tree)))
        goto ROLL_BACK;

    if (0 == domain_rbtree_to_text_helper(buf, tree->root_, 1))
        goto ROLL_BACK;

    return buffer_position(buf) - roll_back_pos;

ROLL_BACK:
    buffer_set_position(buf, roll_back_pos);
    buffer_write_u8(buf, 0);
    return 0;

}

static uint32_t
domain_rbtree_to_text_helper(buffer_t *buf, domain_rbnode_t *node, uint32_t depth)
{
    uint32_t start_pos = buffer_position(buf);
    uint32_t len = 0;
    if (DOMAIN_RBNODE_IS_NULL(node))
    {
        INDENT(buf, depth, len);
        if (len == 0) return 0;
        if (0 == buffer_printf(buf, "%s", "NULL\n"))
            return 0;
        return buffer_position(buf) - start_pos;
    }

    INDENT(buf, depth, len);
    if (len == 0) return 0;
    if (0 == wire_name_to_text(node->name_, buf))
        return 0;
    if (0 == buffer_printf(buf, "(%s)%s", node->color_ == BLACK ? "black" : "red",
                domain_rbnode_is_empty(node) ? "[invisible]\n" : "\n"))
        return 0;

    if (!DOMAIN_RBNODE_IS_NULL(node->down_)) {
        INDENT(buf, depth + 1, len);
        if (len == 0) return 0;
        if (0 == buffer_printf(buf, "%s", "begin down from "))
            return 0;
        if (0 == wire_name_to_text(node->name_, buf))
            return 0;
        if (0 == buffer_printf(buf, "%s", "\n"))
            return 0;
        domain_rbtree_to_text_helper(buf, node->down_, depth + 1);
        INDENT(buf, depth + 1, len);
        if (len == 0) return 0;
        if ( 0 == buffer_printf(buf, "%s", "end down from ")) 
            return 0;
        if (0 == wire_name_to_text(node->name_, buf))
            return 0;
        if (0 == buffer_printf(buf, "%s", "\n"))
            return 0;
    }

    uint32_t left_len = domain_rbtree_to_text_helper(buf, node->left_, depth + 1);
    uint32_t right_len = domain_rbtree_to_text_helper(buf, node->right_, depth + 1);
    if (left_len == 0 || right_len == 0)
        return 0;
    return left_len + right_len;
}



